/*---------------------------------------------------------------------*\
|			CACHE Implementation  ZONE
\*---------------------------------------------------------------------*/


#include "cache.h"
#include "debug.h"

namespace Tablebases
{

bool_t			DTM_CACHE_INITIALIZED = FALSE;
int				WDL_FRACTION = 64;
int				WDL_FRACTION_MAX = 128;
size_t			DTM_cache_size = 0;
size_t			WDL_cache_size = 0;
unsigned int		TB_AVAILABILITY = 0;
bool_t 			Uncompressed = TRUE;
extern uint64_t Bytes_read = 0;


extern void
split_index (size_t entries_per_block, index_t i, index_t *o, index_t *r)
{
	index_t n;
	n  = i / (index_t) entries_per_block;
	*o = n * (index_t) entries_per_block;
	*r = i - *o;
	return;
}



/*---------------------------------------------------------------------*\
|			WDL CACHE Maintainance
\*---------------------------------------------------------------------*/


struct WDL_CACHE 	wdl_cache = {FALSE,0,0,NULL,
								 NULL,NULL,0,NULL,
								 0,0,0,0,0,0};

static size_t
wdl_cache_init (size_t cache_mem)
{
	unsigned int 	i;
	wdl_block_t 	*p;
	size_t 			entries_per_block;
	size_t 			max_blocks;
	size_t 			block_mem;

	if (WDL_CACHE_INITIALIZED)
		wdl_cache_done();

	entries_per_block 	= DTM_entries_per_block;  /* fixed, needed for the compression schemes */

	WDL_units_per_block	= entries_per_block / WDL_entries_per_unit;
	block_mem			= WDL_units_per_block * sizeof(unit_t);

	max_blocks 			= cache_mem / block_mem;
	cache_mem 			= max_blocks * block_mem;


	wdl_cache_reset_counters ();

	wdl_cache.entries_per_block = entries_per_block;
	wdl_cache.max_blocks 		= max_blocks;
	wdl_cache.cached 			= TRUE;
	wdl_cache.top 				= NULL;
	wdl_cache.bot 				= NULL;
	wdl_cache.n 				= 0;

	if (0 == cache_mem || NULL == (wdl_cache.buffer = (unit_t *) malloc (cache_mem))) {
		wdl_cache.cached = FALSE;
		return 0;
	}

	if (0 == max_blocks|| NULL == (wdl_cache.blocks = (wdl_block_t *) malloc (max_blocks * sizeof(wdl_block_t)))) {
		wdl_cache.cached = FALSE;
		free (wdl_cache.buffer);
		return 0;
	}
	
	for (i = 0; i < max_blocks; i++) {
		p = &wdl_cache.blocks[i];
		p->key  	= -1;
		p->fileoffset = gtbNOINDEX;
		p->offset 	= gtbNOINDEX;
		p->p_arr 	= wdl_cache.buffer + i * WDL_units_per_block;
		p->prev 	= NULL;
		p->next 	= NULL;
	}

	WDL_CACHE_INITIALIZED = TRUE;

	return cache_mem;
}


static void
wdl_cache_done (void)
{
	assert(WDL_CACHE_INITIALIZED);

	wdl_cache.cached = FALSE;
	wdl_cache.hard = 0;
	wdl_cache.soft = 0;
	wdl_cache.hardmisses = 0;
	wdl_cache.hits = 0;
	wdl_cache.softmisses = 0;
	wdl_cache.comparisons = 0;
	wdl_cache.max_blocks = 0;
	wdl_cache.entries_per_block = 0;

	wdl_cache.top = NULL;
	wdl_cache.bot = NULL;
	wdl_cache.n = 0;

	if (wdl_cache.buffer != NULL)
		free (wdl_cache.buffer);
	wdl_cache.buffer = NULL;

	if (wdl_cache.blocks != NULL)
		free (wdl_cache.blocks);
	wdl_cache.blocks = NULL;

	WDL_CACHE_INITIALIZED = FALSE;
	return;
}


static void
wdl_cache_flush (void)
{
	unsigned int 	i;
	wdl_block_t 	*p;
	size_t max_blocks = wdl_cache.max_blocks;

	wdl_cache.top 				= NULL;
	wdl_cache.bot 				= NULL;
	wdl_cache.n 				= 0;
	
	for (i = 0; i < max_blocks; i++) {
		p = &wdl_cache.blocks[i];
		p->key  	= -1;
		p->fileoffset = gtbNOINDEX;
		p->offset 	= gtbNOINDEX;
		p->p_arr 	= wdl_cache.buffer + i * WDL_units_per_block;
		p->prev 	= NULL;
		p->next 	= NULL;
	}

	wdl_cache_reset_counters  ();

	return;
}


static void
wdl_cache_reset_counters (void)
{
	wdl_cache.hard = 0;
	wdl_cache.soft = 0;
	wdl_cache.hardmisses = 0;
	wdl_cache.hits = 0;
	wdl_cache.softmisses = 0;
	wdl_cache.comparisons = 0;
	return;
}


extern bool_t
wdl_cache_is_on (void)
{
	return wdl_cache.cached;
}

/****************************************************************************\
|						Replacement
\****************************************************************************/

wdl_block_t*
wdl_point_block_to_replace (void)
{
	wdl_block_t *p, *t, *s;

	assert (0 == wdl_cache.n || wdl_cache.top != NULL);
	assert (0 == wdl_cache.n || wdl_cache.bot != NULL);
	assert (0 == wdl_cache.n || wdl_cache.bot->prev == NULL);
	assert (0 == wdl_cache.n || wdl_cache.top->next == NULL);

	if (wdl_cache.n > 0 && -1 == wdl_cache.top->key) {

		/* top blocks is unusable, should be the one to replace*/
		p = wdl_cache.top;

	} else
	if (wdl_cache.n == 0) {
		
		p = &wdl_cache.blocks[wdl_cache.n++];
		wdl_cache.top = p;
		wdl_cache.bot = p;
	
		p->prev = NULL;
		p->next = NULL;

	} else
	if (wdl_cache.n < wdl_cache.max_blocks) { /* add */

		s = wdl_cache.top;
		p = &wdl_cache.blocks[wdl_cache.n++];
		wdl_cache.top = p;
	
		s->next = p;
		p->prev = s;
		p->next = NULL;

	} else {                       /* replace*/ 
		
		t = wdl_cache.bot;
		s = wdl_cache.top;
		wdl_cache.bot = t->next;
		wdl_cache.top = t;
		
		s->next = t;
		t->prev = s;
		wdl_cache.top->next = NULL;
		wdl_cache.bot->prev = NULL;

		p = t;
	}
	
	/* make the information content unusable, it will be replaced */
	p->key    = -1;
	p->fileoffset = gtbNOINDEX;
	p->offset = gtbNOINDEX;

	return p;
}



extern bool_t
get_WDL_from_cache (tbkey_t key, index_t fileoffset, index_t idx, unsigned int *out)
{
	index_t 	offset;
	index_t		remainder;
	wdl_block_t	*p;
	wdl_block_t	*ret;

	if (!wdl_cache_is_on())
		return FALSE;

	split_index (wdl_cache.entries_per_block, idx, &offset, &remainder); 

	ret = NULL;
	for (p = wdl_cache.top; p != NULL; p = p->prev) {

		wdl_cache.comparisons++;

		if (key == p->key && fileoffset== p->fileoffset && offset  == p->offset) {
			ret = p;
			break;
		}
	}

	if (ret != NULL) {
		*out = wdl_extract (ret->p_arr, remainder); 
		wdl_movetotop(ret);
	}

	FOLLOW_LU("get_wdl_from_cache ok?",(ret != NULL))

	return ret != NULL;
}

static unsigned int
wdl_extract (unit_t *uarr, index_t x)
{
	index_t width = 2;
	index_t nu = x/WDL_entries_per_unit;
	index_t y  = x - (nu * WDL_entries_per_unit);
	return (uarr[nu] >> (y*width)) & WDL_entry_mask;
}

static void
wdl_movetotop (wdl_block_t *t)
{
	wdl_block_t *s, *nx, *pv;

	assert (t != NULL);

	if (t->next == NULL) /* at the top already */
		return;

	/* detach */
	pv = t->prev;
	nx = t->next;

	if (pv == NULL)  /* at the bottom */
		wdl_cache.bot = nx;
	else 
		pv->next = nx;

	if (nx == NULL) /* at the top */
		wdl_cache.top = pv;
	else
		nx->prev = pv;

	/* relocate */
	s = wdl_cache.top;
	assert (s != NULL);
	if (s == NULL)
		wdl_cache.bot = t;	
	else
		s->next = t;

	t->next = NULL;
	t->prev = s;
	wdl_cache.top = t;

	return;
}


/*---------------------------------------------------------------------*\
|			DTM CACHE Maintainance
\*---------------------------------------------------------------------*/

struct cache_table 	dtm_cache = {FALSE,0,0,NULL,
								NULL,NULL,0,NULL,
								0,0,0,0,0,0};


extern bool_t
dtm_cache_is_on (void)
{
	return dtm_cache.cached;
}

static void
dtm_cache_reset_counters (void)
{
	dtm_cache.hard = 0;
	dtm_cache.soft = 0;
	dtm_cache.hardmisses = 0;
	dtm_cache.hits = 0;
	dtm_cache.softmisses = 0;
	dtm_cache.comparisons = 0;
	return;
}


static size_t
dtm_cache_init (size_t cache_mem)
{
	unsigned int 	i;
	dtm_block_t 	*p;
	size_t 			entries_per_block;
	size_t 			max_blocks;
	size_t 			block_mem; 

	if (DTM_CACHE_INITIALIZED)
		dtm_cache_done();

	entries_per_block 	= 16 * 1024;  /* fixed, needed for the compression schemes */

	block_mem 			= entries_per_block * sizeof(dtm_t);

	max_blocks 			= cache_mem / block_mem;
	if (!Uncompressed && 1 > max_blocks)
		max_blocks = 1; 
	cache_mem 			= max_blocks * block_mem;


	dtm_cache_reset_counters ();

	dtm_cache.entries_per_block	= entries_per_block;
	dtm_cache.max_blocks 		= max_blocks;
	dtm_cache.cached 			= TRUE;
	dtm_cache.top 				= NULL;
	dtm_cache.bot 				= NULL;
	dtm_cache.n 				= 0;

	if (0 == cache_mem || NULL == (dtm_cache.buffer = (dtm_t *)  malloc (cache_mem))) {
		dtm_cache.cached = FALSE;
		dtm_cache.buffer = NULL;
		dtm_cache.entry = NULL;
		return 0;
	}

	if (0 == max_blocks|| NULL == (dtm_cache.entry  = (dtm_block_t *) malloc (max_blocks * sizeof(dtm_block_t)))) {
		dtm_cache.cached = FALSE;
		dtm_cache.entry = NULL;
		free (dtm_cache.buffer);
		dtm_cache.buffer = NULL;
		return 0;
	}
	
	for (i = 0; i < max_blocks; i++) {
		p = &dtm_cache.entry[i];
		p->key  	= -1;
		p->fileoffset = gtbNOINDEX;
		p->offset 	= gtbNOINDEX;
		p->p_arr 	= dtm_cache.buffer + i * entries_per_block;
		p->prev 	= NULL;
		p->next 	= NULL;
	}

	DTM_CACHE_INITIALIZED = TRUE;

	return cache_mem;
}


static void
dtm_cache_done (void)
{
	assert(DTM_CACHE_INITIALIZED);

	dtm_cache.cached = FALSE;
	dtm_cache.hard = 0;
	dtm_cache.soft = 0;
	dtm_cache.hardmisses = 0;
	dtm_cache.hits = 0;
	dtm_cache.softmisses = 0;
	dtm_cache.comparisons = 0;
	dtm_cache.max_blocks = 0;
	dtm_cache.entries_per_block = 0;

	dtm_cache.top = NULL;
	dtm_cache.bot = NULL;
	dtm_cache.n = 0;

	if (dtm_cache.buffer != NULL)
		free (dtm_cache.buffer);
	dtm_cache.buffer = NULL;

	if (dtm_cache.entry != NULL)
		free (dtm_cache.entry);
	dtm_cache.entry = NULL;

	DTM_CACHE_INITIALIZED = FALSE;

	return;
}

static void
dtm_cache_flush (void)
{
	unsigned int 	i;
	dtm_block_t 	*p;
	size_t entries_per_block = dtm_cache.entries_per_block;
	size_t max_blocks = dtm_cache.max_blocks;

	dtm_cache.top 				= NULL;
	dtm_cache.bot 				= NULL;
	dtm_cache.n 				= 0;
	
	for (i = 0; i < max_blocks; i++) {
		p = &dtm_cache.entry[i];
		p->key  	= -1;
		p->fileoffset = gtbNOINDEX;
		p->offset 	= gtbNOINDEX;
		p->p_arr 	= dtm_cache.buffer + i * entries_per_block;
		p->prev 	= NULL;
		p->next 	= NULL;
	}
	dtm_cache_reset_counters ();
	return;
}


extern bool_t
get_dtm_from_cache (tbkey_t key, index_t fileoffset, index_t idx, dtm_t *out)
{
	index_t 	offset;
	index_t		remainder;
	bool_t 		found;
	dtm_block_t	*p;

	if (!dtm_cache_is_on())
		return FALSE;

	split_index (dtm_cache.entries_per_block, idx, &offset, &remainder); 

	found = NULL != (p = dtm_cache_pointblock (key, fileoffset, idx));

	if (found) {
		*out = p->p_arr[remainder];
		movetotop(p);
	}

	FOLLOW_LU("get_dtm_from_cache ok?",found)

	return found;
}



static dtm_block_t *
point_block_to_replace (void)
{
	dtm_block_t *p, *t, *s;

	assert (0 == dtm_cache.n || dtm_cache.top != NULL);
	assert (0 == dtm_cache.n || dtm_cache.bot != NULL);
	assert (0 == dtm_cache.n || dtm_cache.bot->prev == NULL);
	assert (0 == dtm_cache.n || dtm_cache.top->next == NULL);

	/* no cache is being used */
	if (dtm_cache.max_blocks == 0)
		return NULL;

	if (dtm_cache.n > 0 && -1 == dtm_cache.top->key) {

		/* top entry is unusable, should be the one to replace*/
		p = dtm_cache.top;

	} else
	if (dtm_cache.n == 0) {
		
		assert (NULL != dtm_cache.entry);
		p = &dtm_cache.entry[dtm_cache.n++];
		dtm_cache.top = p;
		dtm_cache.bot = p;
	
		assert (NULL != p);
		p->prev = NULL;
		p->next = NULL;

	} else
	if (dtm_cache.n < dtm_cache.max_blocks) { /* add */

		assert (NULL != dtm_cache.entry);
		s = dtm_cache.top;
		p = &dtm_cache.entry[dtm_cache.n++];
		dtm_cache.top = p;
	
		assert (NULL != p && NULL != s);
		s->next = p;
		p->prev = s;
		p->next = NULL;

	} else if (1 < dtm_cache.max_blocks) { /* replace*/ 
		
		assert (NULL != dtm_cache.bot && NULL != dtm_cache.top);
		t = dtm_cache.bot;
		s = dtm_cache.top;

		dtm_cache.bot = t->next;
		dtm_cache.top = t;

		s->next = t;
		t->prev = s;

		assert (dtm_cache.top);
		dtm_cache.top->next = NULL;

		assert (dtm_cache.bot);
		dtm_cache.bot->prev = NULL;

		p = t;

	} else {
		
		assert (1 == dtm_cache.max_blocks);
		p =	dtm_cache.top;
		assert (p == dtm_cache.bot && p == dtm_cache.entry);
	}
	
	/* make the information content unusable, it will be replaced */
	p->key    = -1;
	p->fileoffset = gtbNOINDEX;
	p->offset = gtbNOINDEX;

	return p;
}

static void
movetotop (dtm_block_t *t)
{
	dtm_block_t *s, *nx, *pv;

	assert (t != NULL);

	if (t->next == NULL) /* at the top already */
		return;

	/* detach */
	pv = t->prev;
	nx = t->next;

	if (pv == NULL)  /* at the bottom */
		dtm_cache.bot = nx;
	else 
		pv->next = nx;

	if (nx == NULL) /* at the top */
		dtm_cache.top = pv;
	else
		nx->prev = pv;

	/* relocate */
	s = dtm_cache.top;
	assert (s != NULL);
	if (s == NULL)
		dtm_cache.bot = t;	
	else
		s->next = t;

	t->next = NULL;
	t->prev = s;
	dtm_cache.top = t;

	return;
}


extern dtm_block_t	*
dtm_cache_pointblock (tbkey_t key, index_t fileoffset, index_t idx)
{
	index_t 		offset;
	index_t			remainder;
	dtm_block_t	*	p;
	dtm_block_t	*	ret;

	if (!dtm_cache_is_on())
		return NULL;

	split_index (dtm_cache.entries_per_block, idx, &offset, &remainder); 

	ret   = NULL;

	for (p = dtm_cache.top; p != NULL; p = p->prev) {

		dtm_cache.comparisons++;

		if (key == p->key && fileoffset == p->fileoffset && offset  == p->offset) {
			ret = p;
			break;
		}
	}

	FOLLOW_LU("point_to_dtm_block ok?",(ret!=NULL))

	return ret;
}

/*---------------------------------------------------------------------*\
|			CACHE Wrapper Maintainance
\*---------------------------------------------------------------------*/

struct general_counters Drive = {0,0};


extern bool_t
tbcache_is_on (void)
{
	return dtm_cache_is_on() || wdl_cache_is_on();
}


/* STATISTICS OUTPUT */
extern void 
tbstats_get (struct TB_STATS *x)
{
	long unsigned mask = 0xfffffffflu;
	uint64_t memory_hits, total_hits;


	/*
	|	WDL CACHE
	\*---------------------------------------------------*/

	x->wdl_easy_hits[0] = (long unsigned)(wdl_cache.hits & mask);
	x->wdl_easy_hits[1] = (long unsigned)(wdl_cache.hits >> 32);

	x->wdl_hard_prob[0] = (long unsigned)(wdl_cache.hard & mask);
	x->wdl_hard_prob[1] = (long unsigned)(wdl_cache.hard >> 32);

	x->wdl_soft_prob[0] = (long unsigned)(wdl_cache.soft & mask);
	x->wdl_soft_prob[1] = (long unsigned)(wdl_cache.soft >> 32);

	x->wdl_cachesize    = WDL_cache_size;

	/* occupancy */
	x->wdl_occupancy = wdl_cache.max_blocks==0? 0:(double)100.0*(double)wdl_cache.n/(double)wdl_cache.max_blocks;

	/*
	|	DTM CACHE
	\*---------------------------------------------------*/

	x->dtm_easy_hits[0] = (long unsigned)(dtm_cache.hits & mask);
	x->dtm_easy_hits[1] = (long unsigned)(dtm_cache.hits >> 32);

	x->dtm_hard_prob[0] = (long unsigned)(dtm_cache.hard & mask);
	x->dtm_hard_prob[1] = (long unsigned)(dtm_cache.hard >> 32);

	x->dtm_soft_prob[0] = (long unsigned)(dtm_cache.soft & mask);
	x->dtm_soft_prob[1] = (long unsigned)(dtm_cache.soft >> 32);

	x->dtm_cachesize    = DTM_cache_size;

	/* occupancy */
	x->dtm_occupancy = dtm_cache.max_blocks==0? 0:(double)100.0*(double)dtm_cache.n/(double)dtm_cache.max_blocks;

	/*
	|	GENERAL
	\*---------------------------------------------------*/

	/* memory */
	memory_hits = wdl_cache.hits + dtm_cache.hits;
	x->memory_hits[0] = (long unsigned)(memory_hits & mask);
	x->memory_hits[1] = (long unsigned)(memory_hits >> 32);

	/* hard drive */
	x->drive_hits[0] = (long unsigned)(Drive.hits & mask);
	x->drive_hits[1] = (long unsigned)(Drive.hits >> 32);

	x->drive_miss[0] = (long unsigned)(Drive.miss & mask);
	x->drive_miss[1] = (long unsigned)(Drive.miss >> 32);

	x->bytes_read[0] = (long unsigned)(Bytes_read & mask);
	x->bytes_read[1] = (long unsigned)(Bytes_read >> 32);

	// No file management
	// x->files_opened = eg_was_open_count();

	/* total */
	total_hits = memory_hits + Drive.hits;
	x->total_hits[0] = (long unsigned)(total_hits & mask);
	x->total_hits[1] = (long unsigned)(total_hits >> 32);

	/* efficiency */
	{ uint64_t denominator = memory_hits + Drive.hits + Drive.miss;
	x->memory_efficiency = 0==denominator? 0: 100.0 * (double)(memory_hits) / (double)(denominator);
	}
}

extern bool_t
tbcache_init (size_t cache_mem, int wdl_fraction)
{
	assert (wdl_fraction <= WDL_FRACTION_MAX && wdl_fraction >= 0);

	/* defensive against input */
	if (wdl_fraction > WDL_FRACTION_MAX) wdl_fraction = WDL_FRACTION_MAX;
	if (wdl_fraction <                0) wdl_fraction = 0;
	WDL_FRACTION = wdl_fraction;
	
	DTM_cache_size = (cache_mem/(size_t)WDL_FRACTION_MAX)*(size_t)(WDL_FRACTION_MAX-WDL_FRACTION);
	WDL_cache_size = (cache_mem/(size_t)WDL_FRACTION_MAX)*(size_t)     				WDL_FRACTION ;

	#ifdef WDL_PROBE
	/* returns the actual memory allocated */
	DTM_cache_size = dtm_cache_init (DTM_cache_size);
	WDL_cache_size = wdl_cache_init (WDL_cache_size);
	#else
	/* returns the actual memory allocated */
	DTM_cache_size = dtm_cache_init (DTM_cache_size);
	#endif
	tbstats_reset ();
	return TRUE;
}

extern bool_t
tbcache_restart (size_t cache_mem, int wdl_fraction)
{
	return tbcache_init (cache_mem, wdl_fraction);
}

extern void
tbcache_done (void)
{
	dtm_cache_done();
	#ifdef WDL_PROBE
	wdl_cache_done();
	#endif
	tbstats_reset ();
	return;
}

extern void
tbcache_flush (void)
{
	dtm_cache_flush();
	#ifdef WDL_PROBE
	wdl_cache_flush();
	#endif
	tbstats_reset ();
	return;
}

extern void	
tbstats_reset (void)
{
	dtm_cache_reset_counters ();
	#ifdef WDL_PROBE
	wdl_cache_reset_counters ();
	#endif
	// eg_was_open_reset();
	Drive.hits = 0;
	Drive.miss = 0;
	return;
}

}
